namespace ZIFUCHUAN{

/**
 * @brief 计算[begin, begin + n)区间的特征向量
 *   next[i]记录了 [begin...begin+i] 区间首尾相等的最长真子串的长度
 * @param begin 
 * @param n 
 * @param next 特征向量, 范围[0, n-1]
 */
template<typename IT = const char *>
void calcNext(IT begin, int n, vector<int> & next) {
    next.assign(n, 0);
    for(int i=1;i<n;++i){
        int k = next[i - 1];
        while(k > 0 and *(begin + i) != *(begin + k)){
            k = next[k - 1];
        }
        next[i] = (*(begin + i) == *(begin + k)) ? k + 1 : 0;
    }
    return;
}

/**
 * @brief 计算[begin, begin + n)区间的KMP数
 *   KMP数专门用来在KMP匹配中使用，比原始特征向量更快
 *   KMP数组比正常特征向量的长度多1，最后一个特征数是假定存在结束标记所计算出的值
 *   所谓结束标记就是不与任何正常元素相等的元素
 * @param begin 
 * @param n 
 * @param next 范围[0, n] 比正常特征向量
 */
template<typename IT = const char *>
void calcKMPNext(IT begin, int n, vector<int> & next) {
    next.assign(n + 1, 0); 
    int k = -1, i = 0;
    next[0] = -1;
    while(i < n){
        while(k >= 0 and *(begin + i) != *(begin + k)) k = next[k];
        ++i, ++k;
        if(i == n) break;
        next[i] = *(begin + i) == *(begin + k) ? next[k] : k;
    }
    next[n] = k;
    return;
}

/**
 * @brief 在[t, t + tn)区间查找是否有[p, p + pn)出现
 *   返回第一个找到的位置距离t的偏移量
 *   对于string类型，可以调用 KMPSearch(T.begin(), T.length(), P.begin(), P.length(), Next)
 *   Next需要调用 calcKMPNext(P.begin(), P.length(), Next)
 *   对于 char[] 类型，可以调用 KMPSearch(T, strlen(T), P, strlen(P), Next)
 * @param t 
 * @param tn 
 * @param p 
 * @param pn 
 * @param next 
 * @return 假设返回r, 则从 t+r 开始找到 p 序列
 *   找不到返回-1
 */
template<typename IT = const char *>
int KMPSearch(IT t, int tn, IT p, int pn, const vector<int> & next){
    assert(pn + 1 == next.size());
    if(tn < pn) return -1;
    int tp = 0, pp = 0;
    while(tp < tn){
        if(-1 == pp or *(t + tp) == *(p + pp)) ++tp, ++pp;
        else pp = next[pp];
        if(pp == pn) return tp - pn;
    }
    return -1;
}

/**
 * @brief 求[p, p+pn)在[t, t+tn)中的出现次数，可以重叠
 *  `aba` 在 `ababa` 中出现了 2 次
 *  注意next要用KMPNext
 * @param t 
 * @param tn 
 * @param p 
 * @param pn 
 * @param next 
 * @param pos 依次保存匹配的位置
 * @return 就是pos的size
 */
template<typename IT = const char *>
int KMPCount(IT t, int tn, IT p, int pn, const vector<int> & next, vector<int> & pos){
    assert(pn + 1 == next.size());
    pos.clear();
    if(tn < pn) return 0;
    int tp = 0, pp = 0, ret = 0;
    while(tp < tn){
        if(-1 == pp or *(t + tp) == *(p + pp)) ++tp, ++pp;
        else pp = next[pp];
        if(pp == pn){
            ret += 1; pp = next[pn];
            pos.emplace_back(tp - pn);
        }
    }
    return ret;
}

/**
 * @brief 求[p, p+pn)在[t, t+tn)中的出现次数，不可重叠
 *  `aba` 在 `ababa` 中出现了 1 次
 *  注意next要用KMPNext
 * @param t 
 * @param tn 
 * @param p 
 * @param pn 
 * @param next next是P的特征向量再在末尾加1
 * @param pos 依次保存匹配的位置
 * @return 就是pos的size
 */
template<typename IT = const char *>
int KMPCount(IT t, int tn, IT p, int pn, const vector<int> & next, vector<int> & pos){
    assert(pn + 1 == next.size());
    if(tn < pn) return 0;
    int tp = 0, pp = 0, ret = 0;
    while(tp < tn){
        if(-1 == pp or *(t + tp) == *(p + pp)) ++tp, ++pp;
        else pp = next[pp];
        if(pp == pn){
            ret += 1; pp = 0;
            pos.emplace_back(tp - pn);
        }
    }
    return ret;
}


}